﻿/************************************************************************
 * AIDE - Automata Identification Engine
 * Copyright (C) 2012-2013 Ali Khalili (khalili_DOT_ir_@SIGN_gmail_DOT_com)
 * **********************************************************************
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License (LGPL) published 
 * by the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version. This program is distributed without any
 * warranty. See the GNU Lesser General Public License for more details. 
 * ***********************************************************************
 * File         :     AIDE\OfflineAlgo\DFAs\OSTIA.cs
 * Description  :     OSTIA (Onward Subsequential Transducer Inference Algorithm) for Mealy machines
 * Change log   :     -Oct 2013:  Initial version
 * To Do        :
 ************************************************************************/
using System;
using System.Collections.Generic;
using AIDE.Utils;
using SMLib.Automata.Base;
using SMLib.Automata.MM;


/// <summary>
/// Online Learning algorithms for regular languages
/// </summary>
namespace AIDE.OfflineAlgo.DFAs
{
    /// <summary>
    /// OSTIA_4MM algorithm (Onward Subsequential Transducer Inference Algorithm) for Mealy machines
    /// <remarks>
    /// Here, we focus on Mealy machine rather than general transducer
    /// </remarks>
    /// </summary>
    public class OSTIA_4MM
    {
        /// <summary>
        /// Samples of sequence
        /// </summary>
        List<Sequence> samples;

        /// <summary>
        /// prefix tree transducer (the starting point of algorithm
        /// </summary>
        Tree<PairOfSymbols> ptt;

        /// <summary>
        /// List of blue nodes and red nodes
        /// </summary>
        List<Tree<PairOfSymbols>.TreeNode> blueNodes, redNodes;

        public OSTIA_4MM(List<Sequence> samples)
        {
            this.samples = samples;
        }

        /// <summary>
        /// Learning function
        /// <remarks>
        /// Based on [Algorithm 18.7 in Book]
        /// </remarks>
        /// </summary>
        /// <returns>The learnt conjecture</returns>
        public MealyMachine Learn()
        {
            BuildPTT();

            MakeItOnward();

            while (blueNodes.Count != 0)
            {
                Tree<PairOfSymbols>.TreeNode q_b = ChooseAndRemove();
                foreach (Tree<PairOfSymbols>.TreeNode q_r in redNodes)
                {
                    if (isCompatible(q_r, q_b))
                    {
                        Merge(q_r, q_b);

                        Promote(q_b);
                        break;
                    }
                }

                //* promote non-red successors of each red states to blue set
                //* ??
            }

            MealyMachine conj = BuildConjecture();
            return conj;
        }

        private MealyMachine BuildConjecture()
        {
            throw new NotImplementedException();
        }

        private void Promote(Tree<PairOfSymbols>.TreeNode q_b)
        {
            throw new NotImplementedException();
        }

        private bool isCompatible(Tree<PairOfSymbols>.TreeNode q_r, Tree<PairOfSymbols>.TreeNode q_b)
        {
            throw new NotImplementedException();
        }

        private Tree<PairOfSymbols>.TreeNode ChooseAndRemove()
        {
            throw new NotImplementedException();
        }


        /// <summary>
        /// Build the prefix tree transducer
        /// </summary>
        void BuildPTT()
        {
            ptt = new Tree<PairOfSymbols>();
            //* build the prefix tree out of positive samples
            foreach (Sequence w in samples)
            {
                //* star from root
                Tree<PairOfSymbols>.TreeNode root = ptt.Root;
                Tree<PairOfSymbols>.TreeNode curr = root;
                //*trace the nodes on tree
                for (int i = 0; i < w.Length; i++)
                {
                    Tree<PairOfSymbols>.TreeNode tmp = curr.ChildByEdge(w[i]);
                    if (tmp == null)
                    {
                        for (int j = i; j < w.Length; j++)
                        {
                            curr = curr.AddChild(w[j]);
                        }
                        break;
                    }
                    else
                        curr = tmp;
                }
            }

            //* set red node as root
            redNodes = new List<Tree<PairOfSymbols>.TreeNode>();
            redNodes.Add(ptt.Root);

            //* set blue nodes as immediate successor of root
            blueNodes = new List<Tree<PairOfSymbols>.TreeNode>();
            blueNodes.AddRange(ptt.Root.Childs);
        }

        /// <summary>
        /// Mealy Machines are always onward!
        /// </summary>
        private void MakeItOnward()
        {
            //* Nothing
        }


        void Merge(Tree<PairOfSymbols>.TreeNode q_r, Tree<PairOfSymbols>.TreeNode q_b)
        {
            q_r.Childs.AddRange(q_b.Childs);
            q_r.Edges.AddRange(q_b.Edges);
            Fold(q_r, q_b);
        }

        void Fold(Tree<PairOfSymbols>.TreeNode q_r, Tree<PairOfSymbols>.TreeNode q_b)
        {

        }
    }
}
